1. Field of the Invention
The invention generally relates to design performance analysis, and more particularly to static timing analysis used in digital design testing.
2. Description of the Related Art
In the technological field relating to static timing analysis, various methods are used to determine whether a digital design satisfies a given set of predefined performance requirements. For performance analysis purposes, the digital design may be represented as a timing graph consisting of nodes and edges. Nodes typically represent pins of circuits comprising the digital design, and edges represent connections between pins, either from source to sink of a wire or from input to output of a logic gate. Each edge has an associated delay (or in some cases a minimum and maximum delay), and a path through the design is a chain of connected nodes and edges from an input of the design to an output of the design. The delay of each edge reflects the time it takes for a signal transition at the source of the edge to cause a signal transition at the sink of the edge, and is caused by the physical characteristics (e.g., capacitances, resistances, threshold voltages, etc.) of the transistors, wires, and other structures in the design. It is well understood that outputs of storage elements of the design (e.g., flip-flops and latches) may be considered starting points for paths, and inputs of storage elements may be considered ending points for paths. The delay or length of the path is the sum of the delays of the edges in the path. A timing graph may also include timing tests (e.g., setup tests), which are requirements that the latest arrival time at one point in the network (e.g., the data pin of a flip-flop or latch) is at least a specified amount (e.g., a setup time) earlier than the earliest arrival time at another point in the network (e.g.; the clock pin of the same flip-flop or latch).
Conventional path-based approaches to static timing analysis trace all (or the top N) paths through a network and then compare the total delay of each path to a predetermined timing specification. However, a disadvantage of path-based approaches is that the number of paths through a digital network (and hence the runtime of the method) can be exponential in the size of the overall network, and thus examination of all paths in real designs may be impossible in practice.
Another conventional approach is to use node-based algorithms in which information regarding only the longest or shortest path is retained at a given node. In this approach an arrival time (AT) is computed for each node X in the design which is the extreme (minimum when determining shortest paths and maximum when determining longest paths) over all predecessor nodes Y (i.e., nodes Y for which an edge from Y to X exists) of the AT of Y plus the delay (minimum delay for shortest path and maximum delay for longest path) of the edge from Y to X.
Use of maximums to determine the longest path is also known as late mode timing analysis, and use of minimums to determine the shortest path is also known as early mode timing analysis. The longest or shortest path to an output can be determined by tracing back from that output along the series of the edges which determined the extreme AT at each node. Well-known methods also exist to determine the N longest or shortest paths in the design or to determine all paths with maximum AT greater than a given value or minimum AT less than a given threshold by using the node-based timing analysis results to trace sub-paths through the design. However, a problem with this approach is that the analysis may miss a path which is significant in its timing delay and which may affect the design performance.
Delays in digital networks may come from a variety of elements (e.g., gates and wires), and can be influenced by a variety of design characteristics. The industry has recognized that the variation in design characteristics is becoming increasingly important, and in fact, it is suggested by industry experts that statistical timing analysis will be a crucial design capability for nanotechnology designs at 90 nm and below. Thus it is important to have static timing analysis methods capable of providing a complete and accurate assessment in design performance evaluation.
For example, suppose a circuit designer sought to gather all paths in the design (regardless of slack) that have greater than X % wire delay and desires to print these paths in slack order. Traditionally, this is a difficult problem with conventional node-based static timing analysis because only the information about the longest or shortest path to a node is retained on that node. However, there may be sub-critical paths (paths which are not the longest or shortest) which have a much higher fraction of wire delay than the longest or shortest path. Thus, no AT threshold can be specified which can be used with conventional node-based methods which ensures that all paths with delays dominated by the factor of interest will be found. In fact, the only known conventional methods known to answer this problem involve tracing all paths in the network; however this may be impractical due to excessive runtimes, as described above.
Other conventional approaches to static timing analysis and design performance evaluation using timing delays are taught in U.S. Pat. No. 5,838,581 issued to Kuroda; U.S. Pat. No. 6,014,510 issued to Burks et al.; U.S. Pat. No. 6,412,101 issued to Chang et al.; and U.S. Pat. No. 6,209,122 issued to Jyu et al., the complete disclosures of which, in their entireties, are herein incorporated by reference. However, while the above-referenced prior art techniques and systems were adequate for the purposes for which they were designed, their solutions have not distinguished between various types of delays in the paths through a network, and have rather focused on the total delay of all the paths. Therefore, there is a need for a novel node-based static timing analysis approach capable of providing a thorough assessment and evaluation of design performance.